Subject: Re: QoS R - best route versus good enough route....

From: [email-masked] (Ariel Orda)
Date: Tue, 29 Apr 1997 17:41:56 +0300

Chotipat,

Thanks for your comments on our work. Here's our reply.

  >
  >First of all, we would like to explain that our main contribution 
  >is if a particular service discipline is considered, the complexity 
  >of QoS routing algorithm could be greately reduced.

We believe this was already pointed out in the two works we mentioned
before, i.e., Infocom'97 paper (full version in IBM Report, July 96)
and Internet Draft (December 96).
	   
  >
  >In my understanding, our algorithm is different of yours, described
  >below.
  >
  >(1)	There is no need of policy to prune link with  
  >	high-propagation delay in our algorithm. Our algorithm can find
  >	a multiple QoS constrained route, if there exists one. 
  >	The propagation delay of the link is used to find the route.
  >	By your Widest-shortest path (the algorithm in section 2.3.1 in
  >	your draft) and policy, you can not guarantee that it could 
  >	always satisfy delay constraint.

In an appendix of the Internet Draft, we show how, without relying on 
pruning, one can compute a path that guarantees a given end-to-end delay
by exploiting the structure of the end to end bound for WFQ and similar 
schedulers.  This had already been pointed out earlier as a special
(deterministic) case of the problem addressed in our Infocom paper.

  >
  >(2)	Your contribution probably is the translation of delay 
  >	requirement to bandwidth requirement. Then use Widest-shortest
  >	path as you proposed. In our algorithm, bandwidth to be reserved
  >	is assumed to known a priori, e.g. peak-rate of requested flow. 

As Qingming pointed out, this approach is very limiting. One of the key 
aspects of the end-to-end delay	 model of the Guaranteed Service, is to 
use the requested service rate as an important knob to obtain the desired 
end-to-end delay bound. Assuming the rate is fixed a priori, eliminates 
this flexibility.

  >	Qingming proposed to run algorithm that we proposed for all of 
  >	the possible residual link bandwidth, if network provider allow
  >	to reserve larger bandwidth than peak-rate. It also can 
  >	guarantee that it could find a route that can satisfy multiple 
  >	QoS constraint in polynomial time, if there exists one.	 The 
  >	bandwidth to be reserved could be computed using your 
  >	delay-to-bandwidth translation (Eq. (2) in the appendix E in
  >	your draft.

Indeed, this is exactly what we had in mind.

  >
  >(3) We also proposed how loss-free constraint could be satisfied.

Yes, this is an interesting observation and certainly one that 
provides further motivations for the model.

Best regards,
Roch and Ariel